package com.itheima.algorithm.sort;

import com.itheima.utils.ArrayTools;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;

//快速排序
public class Quicksort {
    static int count = 0;
    public static void main(String[] args) {
        int[] arr = ArrayTools.getRandomList(10);
        BubbleSortDemo.printArr(arr,"初始数组");
        int[] newArr = Arrays.copyOf(arr,arr.length);


        Long start = System.currentTimeMillis();
        quicksort(arr,0,arr.length-1);
        Long end = System.currentTimeMillis();
        BubbleSortDemo.printArr(arr,"耗时"+(end-start)+"毫秒得出最终结果");

        /*start = System.currentTimeMillis();
        BubbleSortDemo.bubbleSort(newArr);
        end = System.currentTimeMillis();
        BubbleSortDemo.printArr(arr,"耗时"+(end-start)+"毫秒得出最终结果");*/
    }

    private static void quicksort(int[] arr,int left, int right) {
        if (right < left)
            return;
        int left0 = left;
        int right0 = right;

        //计算出基准数
        int baseNumber = arr[left0];
        while (left != right){
            //1.从右开始找比基准数小的数
            while (arr[right] >= baseNumber && right > left){
                right--;
            }

            //2.从左开始找比基准数小的数
            while (arr[left] <= baseNumber && right > left){
                left++;
            }

            //交换两个值的位置
            /*arr[left] = arr[left] ^ arr[right];
            arr[right] = arr[left] ^ arr[right];
            arr[left] = arr[left] ^ arr[right];*/
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;

        }
        //基准数归位
        System.out.println(" arr[left0] = " +  arr[left0] + ",arr[left] = " + arr[left]);
        if (left != left0){
            arr[left] = arr[left] ^ arr[left0];
            arr[left0] = arr[left] ^ arr[left0];
            arr[left] = arr[left] ^ arr[left0];
//        arr[left]和srr[left0]本质上指向同一个数
        }

        /*int temp = arr[left];
        arr[left] = arr[left0];
        arr[left0] = temp;*/
        BubbleSortDemo.printArr(arr,"第"+ ++count + "次排序");
        quicksort(arr,left0,left-1);
        quicksort(arr,left + 1,right0);

    }
}
